#include <iostream>
#include <cstdlib>
#include <vector>

template <typename T>
class BinaryTree
{
private:
    class Node
    {
    public:
	T data;
	Node* lc;
	Node* rc;
	Node* parent;
	Node(T _data);
    };
    Node* root;
    void inorder_walk(Node* _x) const;
    void release(Node* _x);
    Node* successor(Node* _x) const;
    Node* predecessor(Node* _x) const;
    Node* min(Node* _x) const;
    Node* max(Node* _x) const;
    Node* tree_search(T _data, Node* _x);
    void Delete(T _data, Node* _x);
public:
    BinaryTree() {root = NULL;};
    BinaryTree(T _data);
    ~BinaryTree();
    void insert(T _data);
    Node* tree_search(T _data);
    void inorder_walk() const;
    void sort(std::vector<T>&A);
    void test_successor(Node* _x);
    void test_predecessor(Node* _x);
    void test_min();
    void test_max();
    void Delete(T _data);
};

template<typename T>
void BinaryTree<T>::Delete(T _data, Node*_x)
{
	if (_x == NULL)
		std::cout<<"not found"<<std::endl;
	else {
		if (_data < _x->data) {
			Delete(_data, _x->lc);
		}
		else if (_data > _x->data) {
			Delete(_data, _x->rc);
		}
		else {
			if (_x->lc!=NULL && _x->rc!=NULL)
			{
				Node* temp = min(_x->rc);
				_x->data = temp->data;
				Delete(temp->data, _x->rc);
			}
			else
			{
				Node* temp = _x;
				Node* y = _x->parent;
				if (_x->lc == NULL) {
					if (y->lc==_x)
						y->lc = _x->rc;
					else
						y->rc = _x->rc;
				}
				else if (_x->rc == NULL) {
					if (y->lc==_x)
						y->lc = _x->lc;
					else
						y->rc = _x->lc;
				}
				delete temp;
			}
		}
	}
}

template<typename T>
void BinaryTree<T>::Delete(T _data)
{
	Delete(_data, root);
}

template<typename T>
void BinaryTree<T>::sort(std::vector<T>&A)
{
	int n = A.size();
	T B[n];
	for (int i=n;i>0;i--)
	{
		int x;
		x = rand()%i;
		B[n-i] = A[x];
		A[x] = A[i-1];
	}
	for (int j=0; j<n; j++)
		insert(B[j]);
	inorder_walk();
}

template<typename T>
void BinaryTree<T>::test_min()
{
    std::cout << "min: " << min(root)->data << std::endl;
};

template<typename T>
void BinaryTree<T>::test_max()
{
    std::cout << "max: " << max(root)->data << std::endl;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::tree_search(T _data)
{
	tree_search(_data, root);
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::tree_search(T _data, Node* _x)
{
	if (_x == NULL)
		return NULL;
	if (_data < _x->data)
		return tree_search(_data, _x->lc);
	else if (_data > _x->data)
		return tree_search(_data, _x->rc);
	else
		return _x;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::max(Node* _x) const
{
    while (_x->rc != NULL)
		_x = _x->rc;
    return _x;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::predecessor(Node* _x) const
{
    Node* x = _x;
    if (x->lc != NULL)
		return max(x->lc);
    Node* y = x->parent;
    while (y != NULL && x == y->lc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};

template<typename T>
void BinaryTree<T>::test_predecessor(Node* _x)
{
	std::cout << "predecessor : " << predecessor(_x)->data << std::endl;
}

template<typename T>
void BinaryTree<T>::release(Node* _x)
{
    if (_x != NULL)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};

template<typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
    root = NULL;
};

template<typename T>
BinaryTree<T>::Node::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::successor(Node* _x) const
{
    Node* x = _x;
    if (x->rc != NULL)
		return min(x->rc);
    Node* y = x->parent;
    while (y != NULL && x == y->rc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};

template<typename T>
void BinaryTree<T>::test_successor(Node* _x)
{
	std::cout << "successor : " << successor(_x)->data << std::endl;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::min(Node* _x) const
{
    while (_x->lc != NULL)
	_x = _x->lc;
    return _x;
};

template<typename T>
void BinaryTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template<typename T>
void BinaryTree<T>::inorder_walk(Node* _x) const
{
    if (_x != NULL)
    {
	inorder_walk(_x->lc);
	std::cout << _x->data << "\t";
	inorder_walk(_x->rc);
    }
};

template<typename T>
void BinaryTree<T>::insert(T _data)
{
    Node* y = NULL;
    Node* x = root;
    Node* p = new Node(_data);
    while (x != NULL)
    {
	y = x;
	if (p->data  < x->data)
	    x = x->lc;
	else
	    x = x->rc;
    }
    p->parent = y;
    if (y == NULL)
	root = p;
    else if (p->data < y->data)
	y->lc = p;
    else
	y->rc = p;
};

template<typename T>
BinaryTree<T>::BinaryTree(T _data)
{
    Node* p = new Node(_data);
    if (root == NULL)
	root = p;
};
